1. Field of the Invention
The present invention relates to the design of content-addressable memories (CAMs) within computer systems. More specifically, the present invention relates to the design of a CAM with multiple banks that achieves a high average capacity by implementing a priority ordering for insertions into the multiple banks.
2. Related Art
Content-Addressable Memories (CAMs) are used for many purposes in computer systems. For example, CAMs are routinely used to implement commonly-occurring structures in computer systems, such as cache memories, store queues and translation-lookaside buffers (TLBs). However, as computer system performance continues to increase, such CAM structures need to become larger to deal with the performance-limiting effects of growing memory latencies.
However, as CAMs become larger, it is no longer practical to use a “fully-associative” CAM design which has a separate comparator for each memory element. Instead, it is more efficient to use a “set-associative” design, which uses “index bits” in the address to partition the memory elements into subsets, and which provides a small fully-associative memory for each subset. Unfortunately, in cases where the CAM must store everything the system attempts to store (such as in a store queue), if any one of these small fully-associative memories exceeds its capacity, the system has to stall. This “capacity problem” can be somewhat alleviated by using a skewed-associative cache design, which uses a different hash function from each memory bank in the CAM (see A. Seznec, “A Case for Two-Way Skewed-Associative Caches, Proceedings of the 20th International Symposium on Computer Architecture, San Diego, Calif., May 1993.) However, in spite of the advantages of the skewed-associative design, the capacity problem still remains.
Hence, what is needed is a practical CAM design that efficiently handles the capacity problem.